"""
给定一个二叉树，返回其节点值的锯齿形层序遍历。
（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root):   # [1,2,3,4,null,null,5]
        # result = []
        #
        # def dfs(level, count):
        #     tmp = []
        #     if not level: return
        #     for i in range(len(level)):
        #         node = level.pop()
        #         if not node: continue
        #         if count == 0:
        #             tmp.append(node.val)
        #         else:
        #             tmp.insert(0, node.val)
        #         level.insert(0, node.left)
        #         level.insert(0, node.right)
        #     if tmp: result.append(tmp)
        #     if count == 0:
        #         dfs(level, 1)
        #     else:
        #         dfs(level, 0)
        # dfs([root], 0)
        # return result
        result = []
        stack = [root]
        count = 0
        while stack:
            tmp = []
            for i in range(len(stack)):
                node = stack.pop()
                if not node: continue
                if count % 2 == 0:
                    tmp.append(node.val)
                else:
                    tmp.insert(0, node.val)
                stack.insert(0, node.left)
                stack.insert(0, node.right)
            count += 1
            if tmp: result.append(tmp)
        return result







